package hot;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author way
 * @create 2025-03-18 20:18
 */
public class _215__findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (pq.peek() < num) {
                pq.poll();
                pq.offer(num);
            }
        }
        return pq.peek();
    }

    public int findKthLargest_quick(int[] nums, int k) {
        int n = nums.length;// 计算目标索引（从小到大排序时的位置）
        return quickSort(nums, 0, n - 1, k-1);
    }

    int partition(int[] a, int lo, int hi) {
        // 随机选择枢轴并交换到最左端
        int randomIndex = new Random().nextInt(hi - lo + 1) + lo;
        swap(a, lo, randomIndex);
        int v = a[lo];
        while (lo < hi) {
            while (lo < hi && a[hi] <= v) hi--;
            a[lo] = a[hi];
            while (lo < hi && a[lo] >= v) lo++;
            a[hi] = a[lo];
        }
        a[lo] = v;
        return lo;
    }

    int quickSort(int[] a, int lo, int hi, int k) {
        if (hi <= lo) return a[lo];
        int j = partition(a, lo, hi);

        if (j == k) {
            return a[k];
        } else if (j < k) {
            return quickSort(a, j + 1, hi, k);
        } else {
            return quickSort(a, lo, j-1, k);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
